package com.zx._12_算法.排序;

import com.zx._12_算法.Arrs.IAS;

/**
 * @version v1.0
 * @Project: knowledge
 * @Title: Sort4
 * @Description: No.4 希尔排序
 *         对于直接插入排序问题，数据量巨大时。
 *         将数的个数设为n，取奇数k=n/2，将下标差值为k的数分为一组，构成有序序列。
 *         再取k=k/2 ，将下标差值为k的书分为一组，构成有序序列。
 *         重复第二步，直到k=1执行简单插入排序。
 *         https://mp.weixin.qq.com/s/oWvNslQ-NpTlEyOmqtrMQw
 *
 *         时间复杂度：O(n*logn)
 * @author: zhangxue
 * @date: 2019年7月7日下午9:27:41
 * @company: 未知之地
 * @Copyright: Copyright (c) 2019
 */
public class Sort4_希尔排序 implements IAS {

    @Override
    public void sort(int[] nums) {
        int gap = nums.length / 2;
        while (gap >= 1) {
            for (int i = gap; i < nums.length; i++) {
                // 需要插入的数据
                int num = nums[i];

                // 逆向找到位置，也是最后保存数据的位置
                int j = i - gap;
                while (j >= 0 && nums[j] > num) {
                    // 没找到位置，j的数据往后挪一个gap
                    nums[j + gap] = nums[j];
                    j = j - gap;
                }
                nums[j + gap] = num;
            }
            gap = gap / 2;
        }
    }
}
